package com.gaogzhen.datastructure.symbolTable;

import com.gaogzhen.algorithms4.foundation.VisualAccumulator;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * 无须链表实现的符号表
 * @author Administrator
 * @version 1.0
 * @description
 * @date 2022-11-11 20:09
 */
public class SequentialSearchST<K, V> extends AbstractST<K, V>{

    /**
     * 头结点
     */
    private Node<K, V> first;

    /**
     * 符号表键值对数量
     */
    private int size;

    private class Node<K, V> {
        K key;
        V val;
        Node<K, V> next;

        public Node(K key, V val, Node<K, V> next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    @Override
    public void put(K key, V value) {
        int i = 0;
        for (Node<K, V> x = first; x != null; x = x.next) {
            i++;
            if (x.key.equals(key)) {
                x.val = value;
                return;
            }
        }
        first = new Node<>(key, value, first);
        size++;
    }

    @Override
    public V get(K key) {
        for (Node<K, V> x = first; x != null; x = x.next) {
            if (x.key.equals(key)) {
                return x.val;
            }
        }
        return null;
    }

    @Override
    public V delete(K key) {
        Node<K, V> pre = null;
        Node<K, V> p = null;
        V oldVal = null;
        for (Node<K, V> x = first; p == null && x != null; x = x.next) {
            if (x.key.equals(key)) {

                if (pre == null) {
                    p = first;
                    first = first.next;
                } else {
                    p = x;
                    pre.next = x.next;

                }
                oldVal = p.val;
                p.val = null;
                p.next = null;
                size--;
            }
            pre = x;
        }

        return oldVal;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterable<K> keys() {
        Set<K> keySet = new HashSet<>();
        for (Node<K, V> x = first; x != null; x = x.next) {
            keySet.add(x.key);
        }
        return keySet;
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "{}";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('{');
        for (Node<K, V> x = first; x != null; x = x.next) {
            sb.append(x.key).append("=").append(x.val);
            if (x.next != null) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
    }
}
